﻿//你有一个背包，最多能容纳的体积是V。
//现在有n个物品，第i个物品的体积为
//（1）求这个背包至多能装多大价值的物品？
//（2）若背包恰好装满，求至多能装多大价值的物品？​
//输出有两行，第一行输出第一问的答案，第二行输出第二问的答案，如果无解请输出0。
#include <bits/stdc++.h>
using namespace std;
const int n = 1005;
//////解法1（普通二维）：
//dp[i][j]表示到i位置时候，背包体积是不超过j时的最大价值
int dp[n][n]{ 0 };
int main()
{
    int N, V;
    cin >> N >> V;
    vector<pair<int, int>>v(N);
    //ans1：
    for (int i = 0; i < N; i++) cin >> v[i].first >> v[i].second;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= V; j++) {
            dp[i][j] = max(dp[i - 1][j], j >= v[i - 1].first ? dp[i - 1][j - v[i - 1].first] + v[i - 1].second : 0);
        }
    }
    cout << dp[N][V] << endl;
    //ans2：
   //dp[i][j]只是修改了j的含义变成等于j时的最大价值；规定无法填满背包为dp值为-1(与无价值时候的0区分开)

    memset(dp, 0, sizeof dp);
    for (int i = 1; i <= V; i++)dp[0][i] = -1;//由定义可知，当0个位置处，无法填满背包
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= V; j++) {
            //此外每次都要判断要用到的之前的位置是否能填满，也就是dp值不能是-1才能用否则无意义
            //写法一：
            dp[i][j] = max(dp[i - 1][j],
                j >= v[i - 1].first && dp[i - 1][j - v[i - 1].first] != -1 ?
                dp[i - 1][j - v[i - 1].first] + v[i - 1].second : -1);
            //写法二：
              //  dp[i][j]=dp[i-1][j];
              //  if( dp[i-1][j-v[i-1].first]!=-1&&j>=v[i-1].first) 
              //dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i-1].first]+v[i-1].second);
        }
    }
    cout << (dp[N][V] == -1 ? 0 : dp[N][V]) << endl;

    return 0;
}

//解法2（滚动数组优化,降维）：
//原理：
 ////这里相当于把上面的dp二维给覆盖式填表了；由于每次要用到i-1位置的dp值故这里采取的是从右到左的覆盖式填表；可以保证每次取到的是i-1的dp值而并非是i之前填写的dp值。

//// 总结过渡修改方法：1.反向遍历填表
              //2、把dp有关i下标的都干掉
              //3·这里还有个小优化：防止下标越界（如果拿i位置，背包就不会够）：
//如果选它不合适那就不选；也就是对于下标j<v[i-1]即不选让它就是上一次i-1对 应的值 即可；由于我们是覆盖式填表（覆盖上次i-1结果）因此，直接做不操作，即第二次循环只到v[i-1]即可。

int dp[n]{ 0 };
int main()
{
    int N, V;
    cin >> N >> V;
    vector<pair<int, int>>v(N);
    //ans1：
    for (int i = 0; i < N; i++) cin >> v[i].first >> v[i].second;
    for (int i = 1; i <= N; i++) {
        for (int j = V; j >= v[i - 1].first; j--) {
            dp[j] = max(dp[j], dp[j - v[i - 1].first] + v[i - 1].second);
        }
    }
    cout << dp[V] << endl;
    //ans2：
    memset(dp, 0, sizeof dp);
    for (int i = 1; i <= V; i++)dp[i] = -1;
    for (int i = 1; i <= N; i++) {
        for (int j = V; j >= v[i - 1].first; j--) {
            dp[j] = max(dp[j],
                dp[j - v[i - 1].first] != -1 ?
                dp[j - v[i - 1].first] + v[i - 1].second : -1);
        }
    }
    cout << (dp[V] == -1 ? 0 : dp[V]) << endl;

    return 0;
}












